package com.basicalg.impls;

import com.basicalg.helper.AlgHelper;

public class MergeSort {
    private static Comparable[] aux;
    private static void mergeResult(Comparable[] arr, int low, int mid, int hi) {
        int i = low, j = mid +1;

        // copy the origin arr to copy arr aux
        for(int k=low; k<= hi; k++) {
            aux[k] = arr[k];
        }

        for(int k=low; k<=hi; k++) {
            if (i > mid) arr[k] = aux[j++]; //right side
            else if (j > hi) arr[k] = aux[i++]; // left side
            else if (AlgHelper.less(aux[j], aux[i])) arr[k] = aux[j++];
            else arr[k] = aux[i++];
        }
    }

    public static void sort(Comparable[] arr) {
        //// new a copy of arr
        aux = new Comparable[arr.length];
        sort(arr, 0, arr.length);
    }

    private   static  void sort(Comparable[] arr, int low, int hi) {

        if (hi < low ) return;

        int mid = low + (hi - low) /2;

        sort(arr, low, mid); // left sort
        sort(arr, mid, hi); // right sort

        mergeResult(arr,low, mid, hi);

    }

}
